package com.algorithm.cn.linkedlist;

import java.util.Stack;

/***
 * 
* @author wangzonghui
* @date 2020年12月19日 下午5:38:17 
* @Description: 单链表实现
 */
public class SingleLinkedListDemo {
	public static void main(String[] args) {
		System.out.println("单链表测试");
		HeroNode heroNode1 = new HeroNode(1,"宋江","及时雨");
		HeroNode heroNode2 = new HeroNode(2,"卢俊义","玉麒麟");
		HeroNode heroNode3 = new HeroNode(3,"吴用","智多星");
		HeroNode heroNode4 = new HeroNode(4,"林冲","豹子头");
		
		SingleLinkedList singleLinkedList = new SingleLinkedList();
		//加入
//		singleLinkedList.add(heroNode1);
//		singleLinkedList.add(heroNode2);
//		singleLinkedList.add(heroNode3);
//		singleLinkedList.add(heroNode4);
		
		//排序加入
		singleLinkedList.addByOreder(heroNode1);
		singleLinkedList.addByOreder(heroNode4);
		singleLinkedList.addByOreder(heroNode3);
		singleLinkedList.addByOreder(heroNode2);
		
		singleLinkedList.List();
		
		//测试修改结点
		HeroNode newHeroNode = new HeroNode(2,"小卢","玉麒麟~~");
		singleLinkedList.update(newHeroNode);
		System.out.println("~修改后~");
		singleLinkedList.List();
		
		//删除测试
		System.out.println("~删除后~");
		singleLinkedList.del(newHeroNode.no);
		singleLinkedList.List();
		
		//有效链表个数
		System.out.printf("求有效结点链表格式 %d",SingleLinkedList.getLength( singleLinkedList.getHead()));
		
		//获取倒数第几个数据
		System.out.println("查找倒数倒数第一个元素");
		HeroNode res=SingleLinkedList.findLastIndexNode(singleLinkedList.getHead(), 1);
		System.out.println(res.toString());
		
		
		//链表翻转
		System.out.println("~链表翻转~");
		SingleLinkedList.selfReversetList(singleLinkedList.getHead());
		System.out.println("链表大小:"+SingleLinkedList.getLength(singleLinkedList.getHead()));
		singleLinkedList.List();
		SingleLinkedList.reversetList(singleLinkedList.getHead());
		System.out.println("链表大小:"+SingleLinkedList.getLength(singleLinkedList.getHead()));
		singleLinkedList.List();
		
		//逆序打印
		System.out.println("~逆序打印~");
		SingleLinkedList.reversePrint(singleLinkedList.getHead());
	}
	
}

/**
 * @author wangzonghui
 * @date 2020年12月19日 下午5:40:57 
 * @Description:管理链表
 */
class SingleLinkedList {
	
	//初始化头结点，头结点不存放具体数据
	private HeroNode head=new HeroNode(0, "", "");
	
	public HeroNode getHead() {
		return head;
	}
	
	/**
	 * 添加结点向单向链表
	 * 1. 找当前链表的最后结点
	 * 2. 将最后结点的next指向新结点
	 * @param hernoe
	 */
	public void add(HeroNode heroNode) {
		
		HeroNode tmp=head;
		while(true) {
			//找到最后一个结点
			if(tmp.next==null) {
				break;
			}
			//后移
			tmp=tmp.next;
			
		}
		tmp.next=heroNode;
	}
	
	/**
	 * 自己实现单链表翻转
	 * 新定义一个头，每次将当前节点放入头，当前节点的下一个为头原本的下一个
	 * 
	 */
	public static void reversetList(HeroNode head) {
		//判断是否为空
		if(head.next==null||head.next.next==null) {
			System.out.println("翻转：链表为空");
			return;
		}
		
		HeroNode tmp=head.next;
		HeroNode reverseHead= new HeroNode(0,"","");
		HeroNode next=null;  //指向当前节点的下一个下一个结点
		while(tmp!=null) {
			next=tmp.next;
			tmp.next=reverseHead.next; //当前指向头的next，相当于每次替换头的下一个
			reverseHead.next=tmp;
			tmp=next;
		}
		head.next=reverseHead.next;
		
	}
	
	//方式二 利用栈先进后出特点，实现逆序打印
	public static void reversePrint(HeroNode head) {
		//判断是否为空
		if(head.next==null) {
			System.out.println("翻转：链表为空");
			return;
		}
		
		//创建要给一个栈，将各个节点压入栈
		Stack<HeroNode> stack=new Stack<>();
		HeroNode cur=head.next;
		//将链表的所有节点压入栈
		while(cur!=null) {
			stack.push(cur);
			cur=cur.next;
		}
		
		//出栈
		while(stack.size()>0) {
			System.out.println(stack.pop());
		}
		
	}
	
	/**
	 * 自己实现单链表翻转
	 * 原算法定义，每次循环包含上一个，当前，和下一个。
	 * 保存当前节点，next替换为上个节点，取出下一个结点继续循环
	 * 
	 */
	public static void selfReversetList(HeroNode head) {
		//判断是否为空
		if(head.next==null||head.next.next==null) {
			System.out.println("翻转：链表为空");
			return;
		}
		
		HeroNode tmp=head.next;
		HeroNode other = null;
		HeroNode next=null;  //指向当前节点的下一个下一个结点
		while(true) {
			next=tmp.next;
			if(head.next.no==tmp.no) {  //第一个
				tmp.next=null;

			}else{   //其他
				//tmp next需要修改
				tmp.next=other;
				//返回当前节点下一个接单
				if(next==null) {  //最后一个
					head.next=tmp;
					break;
				}
			}
			other=tmp;
			tmp=next;
			
		}
		
	}
	
	/**
	 * 排序添加节点
	 * @param heroNode
	 */
	public void addByOreder(HeroNode heroNode) {
		//找到为添加位置的下个结点
		HeroNode tmp=head;
		boolean flag=false;  //添加的编号是否存在默认为false
		while(true) {
			if(tmp.next==null) {
				break;
			}
			if(tmp.next.no>heroNode.no) {
				break;
			}else if(tmp.next.no==heroNode.no) {
				flag=true;  //编号存在
			}
			
			tmp=tmp.next;
		}
		
		//判断flag值
		if(flag) {
			System.out.printf("待插入英雄编号%d已存在，不能加入",heroNode.no);
		}else {
			heroNode.next=tmp.next;
			tmp.next=heroNode;
		}
		
	}
	
	/**
	 * 修改 根据标号修改
	 * @param heroNode
	 */
	public void update(HeroNode newHeroNode) {
		//判断是否为空
		if(head.next==null) {
			System.out.println("链表为空");
			return;
		}
		
		//找到需要修改的结点
		HeroNode tmp=head.next;
		boolean flag=false;  //表示是否找到
		while(true) {
			//链表遍历结束
			if(tmp==null) {
				break;
			}
			
			//找到
			if(tmp.no==newHeroNode.no) {
				flag=true;
				break;
			}
			
			tmp=tmp.next;
		}
		
		if(flag) {
			tmp.name=newHeroNode.name;
			tmp.nickName=newHeroNode.nickName;
			
		}else {  //没有找到
			System.out.printf("没有找到 编号%d 的结点，不能修改",newHeroNode.no);
		}
		
	}
	
	/**
	 * 删除节点
	 * @param newHeroNode
	 */
	public void del(int no) {
		//找到需要修改的结点
		HeroNode tmp=head;
		boolean flag=false;  //表示是否找到
		while(true) {
			//链表遍历结束
			if(tmp==null) {
				break;
			}
			
			//找到
			if(tmp.next.no==no) {
				flag=true;
				break;
			}
			
			tmp=tmp.next;
		}
		
		if(flag) {  //删除
			tmp.next=tmp.next.next;
			
		}else {  //没有找到
			System.out.printf("没有找到 编号%d 的结点，不能删除",no);
		}
	}
	
	/**
	 * 遍历链表
	 */
	public void List() {
		if(head.next==null) {
			System.out.println("链表为空");
			return;
		}
		
		HeroNode tmp=head.next;
		while(true) {
			//找到最后一个结点
			if(tmp==null) {
				break;
			}
			System.out.println(tmp);
			//如果没有找到最后
			tmp=tmp.next;
		}
	}
	
	/**
	 * 查找倒数第几个数据
	 * @param head
	 * @param index
	 * @return
	 */
	public static HeroNode findLastIndexNode(HeroNode head,int index) {
		if(head.next==null) {  //空链表
			return null;
		}
		
		//获取有效数据长度
		int size=getLength(head);
		//范围效验
		if(index<=0||index>size) {
			return null;
		}
		
		//定义辅助遍历
		HeroNode cur=head.next;
		for(int i=0;i<size-index;i++) {
			cur=cur.next;
		}
		
		return cur;
	}
	/**
	 * 获取有效结点的个数
	 * @param head 链表的头结点
	 * @return
	 */
	public static int getLength(HeroNode head) {
		if(head.next==null) {  //空链表
			return 0;
		}
		
		int length=0;
		HeroNode cur=head.next;
		while(cur!=null) {
			length++;
			cur=cur.next;
		}
		return length;
	}
}
/**
 * 
* @author wangzonghui
* @date 2020年12月19日 下午5:39:25 
* @Description:英雄了
 */
class HeroNode{
	
	public int no;
	public String name;
	public String nickName;
	public HeroNode next;
	
	public HeroNode(int no,String name,String nickName) {
		this.no=no;
		this.name=name;
		this.nickName=nickName;
	}
	
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
	}
}
